public class HashBuck {
	/**
	 * 这个哈希表是基本数据类型，不是泛型的，不需要进行重写hascode和equals方法
	 */
	static class Node {
		public int key;
		public int val;
		public Node next;

		public Node(int key, int val) {
			this.key = key;
			this.val = val;
		}
	}
	public Node [] array;
	public int usedSize;

	public HashBuck() {
		array=new Node [10];
	}

	/**
	 * 在插入时候，如果负载因子过大，就需要进行扩容
	 * 扩容我们需要把每个节点重新进行哈希函数，重新进行定位，然后再将新的引用赋值给原来的引用
	 * //  避免冲突：1.选择合适哈希函数
	 *              2.及时调整负载因子，就是扩大数组的长度
	 *     解决冲突：1.闭散列：线性探测和二次探测，
	 *              线性探测的时候如果遇到14和24，24就要排到14后面，此时要删除14时，也不敢进行删除因为删除了14，我们找24该如何找呢
	 *              线性探测的时候，会导致数据集中在一起，空间利用率比较低。
	 *              2.开散列
	 *              具有相同地址的关键码归于一个字集合，每个字集合称为一个桶，各个桶中的元素通过一个单链表链接起来
	 *              各链表的头节点存储在哈希表中
	 *              当冲突严重的时候，每个链表就变成了搜索树
	 * @param key
	 * @param val
	 */
	public void put(int key,int val) {
		int index=key%array.length;
		Node node=new Node(key,val);
		//哈希表的话，如果存在的话，就需要更新它的val值
		//不存在的话，就需要插入这个的值
		Node cur=array[index];
		while(cur!=null) {
			if(cur.key==key) {
				cur.val=val;
				return ;
			}
			cur=cur.next;
		}
		//程序走到这里说明没有这个key
		node.next=array[index];
		array[index]=node;
		usedSize++;
		if(loadFactor()>0.75) {
			resize();
		}
	}
	private void resize() {
		Node []tempArr=new Node[array.length*2];
		for(int i=0;i<array.length;i++) {
			Node cur=array[i];
			while(cur!=null) {
				//先记录下来下一个节点
				Node curNext=cur.next;
				int index=cur.key%tempArr.length;
				//进行头插
				cur.next=tempArr[index];
				tempArr[index]=cur;
				cur=curNext;
			}
		}
		array=tempArr;
	}
	private double loadFactor() {
		return usedSize*1.0/this.array.length;
	}
	public int get(int key) {
		int index=key%array.length;
		Node cur=array[index];
		while(cur!=null) {
			if(cur.key==key) {
				return cur.val;
			}
			cur=cur.next;
		}
		return -1;
	}
}
